Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,

Given:

s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.

When s3 = "aadbbbaccc", return false.

Solution:

  1. public class Solution {
  2.   public boolean isInterleave(String s1, String s2, String s3) {
  3.     int n1 = s1.length(), n2 = s2.length(), n3 = s3.length();
  5.     if (n1 + n2 != n3)
  6.       return false;
  8.     boolean[][] dp = new boolean[n1 + 1][n2 + 1];
  10.     dp[0][0] = true;
  12.     // first row
  13.     for (int j = 1; j <= n2; j++) {
  14.       dp[0][j] = (s2.charAt(j - 1) == s3.charAt(j - 1)) && dp[0][j - 1];
  15.     }
  17.     // first col
  18.     for (int i = 1; i <= n1; i++) {
  19.       dp[i][0] = (s1.charAt(i - 1) == s3.charAt(i - 1)) && dp[i - 1][0];
  20.     }
  22.     // others
  23.     for (int i = 1; i <= n1; i++) {
  24.       for (int j = 1; j <= n2; j++) {
  25.         dp[i][j] = ((s1.charAt(i - 1) == s3.charAt(i + j - 1)) && dp[i - 1][j]) || 
  26.                    ((s2.charAt(j - 1) == s3.charAt(i + j - 1)) && dp[i][j - 1]);
  27.       }
  28.     }
  30.     return dp[n1][n2];
  31.   }
  32. }